package basic.sort;

import java.util.Arrays;

/**
 * @创建人 MBY381
 * @创建时间 2022/3/28 15:09
 * @描述 暂无
 */
public class MergeSort {
    public static int[] merge_Sort(int[] sourceArray) {
        // 对arr进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        if (arr.length < 2) return arr;

        int middle = (int) Math.floor(arr.length / 2);
        int[] left = Arrays.copyOfRange(arr, 0, middle);//左子序列
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);//右子序列

        return merge(merge_Sort(left), merge_Sort(right));
    }

    public static int[] merge(int[] left, int[] right) {
        int result[] = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }
        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }
        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        return result;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{0xE3, 381, 8, 6, 4, 7, 9, 3, 5, 2, 1, 782, 696, 259, 0x15};
        System.out.println("正确答案：    [1, 2, 3, 4, 5, 6, 7, 8, 9, 21, 227, 259, 381, 696, 782]");
        merge_Sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
